第十五天 Deadlocks(死結)--中

今天我們來說如何處理deadlock吧！
處理deadlock的方法有四種：Prevention、Avoidance、Detection跟Ignore

1. Prevention(預防)：設計時就不讓deadlock產生
   如果要用預防這個方法會比較辛苦，他就要針對我們上一篇所說形成deadlock的四個條件做處理。

   • Mutual Exclusion：
     對於不共用資源，必會互斥(但這通常不可能可以預防，因為有的還是會需要運用到共用資源)。
   • Hold and Wait：
     Process必須保證必須保證在要求一項資源時，不能佔用其他資源，除非他可以一次取得所有資源。
   • No Preemption：
     只要process握著一些資源，但得不到其他的，就要先全部釋放，再重新申請。
   • Circular Wait：
     對resource type強制安排線性順序，不讓circular wait的條件達成。

2. Avoidance(避免)：有可能會發生deadlock，但盡量避免

   在avoidance前system必須要知道的事有：

   1. 每個process要知道對不同resource type需要多少，這是最重要的
   2. 用deadlock-avoidance演算法檢查時，要確定不會有circular wait的狀況發生。
   3. 在資源分配時要看狀況，再決定是不是要再給resource。

   Safe state是判斷system是否是安全狀態，如果所有process在要求resource時，都能照順序就不會有circular wait和deadlock的情形。也就是說如果有process1要資源時，並不用立刻要求，可以等到另外一個process2用完。而process2用完歸還後，還能拿到下一個要使用的resource。System如果在safe state，那他一定沒有deadlock，但如果在unsafe state，那他就有可能會發生deadlock。Avoidance就是確保system不會進到unsafe state。

   Avoidance的演算法分為兩種：

   1. Resource-Allocation Graph(RAG)：如果resource type只有一個instance
   2. Banker’s algorithm：如果resource type有多個instance

   Resource-Allocation Graph：
   產生時有個標準：

   • 當process要向resource產生要求時，claim edge會出現
   • 當process要求resource時，claim edge就會變成request edge
   • 當resource要給process時，request edge就會變成assignment edge
   • 當process釋放resource時，assignment edge就會變成claim edge

   在這裡process也必須先知道要多少resource，而且只有在不形成cycle時才能接受請求。以下是不安全的RAG：
   
   Banker’s algorithm：

   在使用前有些事要注意，1. 就是每個process要預先知道運用多少resource 2. Process要求resource時，需要等待 3. 當process用完resource時，要return回去

   Banker’s algorithm的資料結構為：
   假設有n個process，m個resource type

   • available[1…m]：表示resource type還有幾個instance可以使用
   • max[1…n,1…m]：表示process需要最多幾個resource type的instance(二維)
   • allocation[1…n,1…m]：表示process現在握有幾個resource type的instance(二維)
   • need[1…n,1…m]：表示process現在還要多少resource type的instance(二維)。need[1…n,1…m] ＝ max[1…n,1…m] - allocation[1…n,1…m]

   判斷是不是safety的演算法，是用兩個暫時的陣列Work(代表resource type)和Finish[i](代表process是否執行完成，i = 0,1,…,n-1)：

   1. Work的初始值設為Available，Finish[i]=false
   2. 看i是不是執行完畢跟Needi<=Worki，如果i不存在直接跳第四步
   3. 將Work + Allocationi形成新的work，看Finish[i]是否＝true，true就回去第二步繼續看下一個process
   4. 如果所有i都完成，則是一個safe狀態

   判斷resource-request演算法是否安全，用下面幾個步驟判別：
   Request i = Process i的request vector
   Request i [j] = k -> Pi要Rj內k個instance

   1. Requesti <= Needi ->第二步，其餘就是要求的超過需要的(出錯)
   2. Requesti <= Allocationi -> 第三步，其餘就是要求的超過剩餘的(要等)
   3. 計算：
      Available = Available - Requesti
      Allocationi = Allocationi + Requesti
      Needi = Needi - Requesti
      再執行safety algorithm

   如果結果計算出來是safe，resource可以分配給process; 如果結果計算出來是unsafe，那process就還要繼續等，而且要把舊的resource-allocation state結束掉。

   以下有例題及運算：
   有5個process，3個resource type(A有10個instance、B有5個instance、C有7個instance)
   
   如果process照著順序做完，那system就是在safe state(會釋放instance)。

   像下面第一張圖，Ｐ1要先request(1,0,2)，他一樣也可以繼續進行，因為instance還夠用，但如果現在是Ｐ4要先request(3,3,0)那就不行，因為現有的instance不足。而第二張圖是Ｐ0要先request(0,2,0)，如果照第一張圖的順序是unsafe的，要換成另外一種執行順序才可以。
   
   
   剩下兩個我們明天繼續加油！